package com.zjsru.plan2023.oneday;

/**
 * @Author: cookLee
 * @Date: 2023-09-07
 * 修车的最少时间
 * \
 * 给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
 * 同时给你一个整数 cars ，表示总共需要修理的汽车数目。
 * \
 * 输入：ranks = [4,2,3,1], cars = 10
 * 输出：16
 * 解释：
 * - 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
 * - 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
 * - 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
 * - 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
 * 16 分钟是修理完所有车需要的最少时间。
 * \
 * 输入：ranks = [5,1,8], cars = 6
 * 输出：16
 * 解释：
 * - 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
 * - 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
 * - 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
 * 16 分钟时修理完所有车需要的最少时间。
 */
public class RepairCars {

    /**
     * 二分法
     * @param ranks
     * @param cars
     * @return long
     */
    public long repairCars(int[] ranks, int cars) {
        long left = 1;
        //最大修车时间最少为l=1，最大是所有车交给一个工人r=ranks[0] * cars * cars。
        long right = 1l * ranks[0]*cars*cars;
        while(left < right){
            long mid = left+right >> 1;
            if(this.helper(ranks,cars,mid)){
                //当前所需时间太大，需要缩小范围
                right = mid;
            }else{
                //增加时间范围
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 计算助手类:获取当前能力下能够修车的数量
     * @param ranks
     * @param cars
     * @param mid
     * @return boolean
     */
    private boolean helper(int[] ranks, int cars, long mid) {
        long  sum = 0;
        for (int rank : ranks) {
            sum += (long) Math.sqrt(mid / rank);
        }
        return sum >= cars;
    }

    public static void main(String[] args) {
        RepairCars repairCars = new RepairCars();
        int[] ranks = new int[]{1,4,2,3};
        int cars = 10;
        System.out.println(repairCars.repairCars(ranks, cars));

    }
}
